package sol.leetcode;

import def.TreeNode;

/**
 * House Robber III
 */
public class Issue337 {
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return root.val;

        //case 1:rob root
        int include = root.val;
        if (root.left != null) {
            include += rob(root.left.left);
            include += rob(root.left.right);
        }
        if (root.right != null) {
            include += rob(root.right.left);
            include += rob(root.right.right);
        }

        //case 2:don't rob root
        int exclude = rob(root.left) + rob(root.right);

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        //TreeNode node1 = new TreeNode(3);
        //TreeNode node2 = new TreeNode(2);
        //TreeNode node3 = new TreeNode(3);
        //TreeNode node4 = new TreeNode(3);
        //TreeNode node5 = new TreeNode(1);
        //node1.left = node2;
        //node1.right = node3;
        //node2.right = node4;
        //node3.right = node5;

        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(1);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.right = node5;
        node3.right = node6;
        Issue337 sol = new Issue337();

        System.out.println(sol.rob(node1));
    }
}
